Summing a List of Lists¶
Recursion…but only when it’s needed¶
In the preceding section on detecting palindromicity, we wrote code where we didn’t need to run through all the possible recursive cases. In the case of pal(), if at any point s[0] != s[-1], we returned False and sent the entire recursive cascade into reverse, without ever reaching the base case. We were able to do this by moving away from the simplest implementation of recursion, which can be represented as:
def foo(n):
if base case is True:
return base case
else:
return foo(#modified n)
Now we have something a little more nuanced:
def foo(n):
if base case:
return True
else:
if #some condition:
return foo(#modified n)
else:
return False
One of the drawbacks of teaching recursion with only the most common examples (ie, factorial, Fibonacci) is that these examples write the recursive call as part of the return statement. For those algorithms, it’s appropriate that the ‘return + recursive call’ statement drives the entire post-recursive program flow. Recursion is about much more than just having a ‘return + recursive call’ statement at the end of your function. As pal() made clear, recursive calls can work in harmony with other operations to reach an answer.
If we can place the ‘return + recursive call’ construction anywhere we need within the function, then it stands to reason that recursive calls can be entirely separate from return statements, too. We’ve already started to peel this apart in Counting In Recursion by creating an intermediate variable r in order to print out the post-recursive portion of the cascade. Now consider a scenario where you want to return the value generated by a recursive call, but also need to perform an additional computation on that value with a specific value in each frame. To illustrate, here is another example, and one where recursion really begins to shine.
Say we have a list L of integers, and we want to return the sum. However, some of these integers sit in sublists within L. We can’t use Python’s sum() method, since it requires that the list be ‘flat’ - we get a Type Error if we try to sum an integer with a list. While we know that our input will only contain integers, those integers could be contained in lists within lists within lists, oh my.
If we knew that we would only be getting a list with lists inside it - call it a ‘depth of two’ for the sake of convenience - then it wouldn’t be hard to write an iterative solution:
def sumListIter(L):
total = 0
for e in L:
if isinstance(e, int):
total += e
else:
for e in e:
total += e
return total
L = [[1, 2], 3, [4, 5]]
print(sumListIter(L))
>>> 15
Unfortunately, if we appended [[6]] to L we’d be out of luck. We could keep writing for loops to intercept varying depths of nestedness but things will get ugly quickly, and ugly code is always difficult to maintain. Also, there could always be a depth that we hadn’t thought to cover, like [[[[[2]]]]].
How would we approach this recursively? Let’s start with some pseudo-code:
- Iterate over the items in list
L - If an item is a list, iterate over it and add it to
total - Else an item is an integer, so add it to
total - When there are no more items in
L, returntotal
Admittedly, this second step is a bit of a puzzle. How can we iterate over a list if we’ve already passed step 1), which is the point in the function where we iterate over a list? It’s precisely here that recursion comes in. We can rewrite the second step as a call back to the first step:
- Iterate over the items in list
L - If an item is a list, send it to step 1.
- Else an item is an integer, so add it to
total - When there are no more items in
L, returntotal
Before we translate this into code, we have to answer a few questions. How do we know whether a variable represents an integer or a list? You have probably used the type() method to figure out what a particular variable or constant is:
x = 6
type(x)
>>> <class 'int'>
type(6)
>>> <class 'int'>
type([6])
>>> <class 'list'>
An empty list is still a list, of course:
type([])
>>> <class 'list'>
So for some element e in list L, let’s use this syntax to our advantage to translate the first two lines of our pseudocode:
def sumListRecur(L):
for e in L:
if type(e) == type([]):
sumListRecur(e)
We add the third line of our pseudocode to cover for when e is an integer, and declare a variable total to collect the sums. Finally, we add the fourth line, which is the return statement:
def sumListRecur(L):
total = 0
for e in L:
if type(e) == type([]):
sumListRecur(e)
else:
total += e
return total
If we run it with L = [1, 2, [11, 13], 8, [4, [4, 5, 5]], [[5, []]]] as our list, we get
>>> 11
Uh-oh. We still seem to be adding only the items in the list that are not in nested lists. Can you see what’s wrong in the code?
Something was lost in translation in the two versions of pseudo-code: total. That is, the recursive call sumListRecur(e) needs a container in which to dump its result. If you go back to the last section of Scope, Frame and Stack, we can only change a variable’s namespace by explicitly binding the new value to the variable. This simple fix does the trick:
def sumListRecur(L):
total = 0
for e in L:
if type(e) == type([]):
total += sumListRecur(e)
else:
total += e
return total
>>> 58
Let’s unpack this code now, as it has a few interesting details.
The first point is the recursive call itself. As we iterate over each e item in L, when we identify an instance where e == type([]), we only need to send that specific e as an argument for the recursive function. In this way, we have the same function sumListRecur() address a smaller version (e) of the total problem (L) - which is pretty much the point of recursion. Moreover, we do this only when we need to, since if e is not a list, it must be an integer, in which case it is added to total during the else block.
In the majority of recursive cases seen so far, we have been passing arguments that have either predictably decremented to the base case (eg, summ() and factorial()), or we have sent ever-smaller slices of a defined string (pal()). In the case of pal() this process of decrementation is also fundamentally predictable - the maximum number of slices, if the string is in fact a palindrome, is always len(s) // 2. Only gcdRecur() is unpredictable in terms of the number of steps it takes to get to the base case, but the recursive call drives the algorithm to the base case regardless.
With sumListRecur() plenty of work is being done without recursion. Indeed, this program could compute a flat list without resorting to recursion at all. On the other hand, as long as ``e`` is a list, the recursive call will get triggered. In this way, a deeply nested list, such as [[[5, []]]] is as easily handled as a flat list.
If recursion is being deployed on an as-needed basis, that means that we may well hit the base case multiple times in the course of processing a list. This may sound trivial, but so far all of our algorithms have engaged recursion in a fairly linear fashion - a sort of ‘one and done’ approach. It’s valuable to recognize that you can use recursion only when you need it, and as often as you need it, within a single algorithm.
Computing values inside each recursive frame¶
The use of total deserves a fuller description. Recall the iterative code with which we started:
def sumListIter(L):
total = 0
for e in L:
if isinstance(e, int):
total += e
else:
for e in e:
total += e
return total
And compare it with our recursive code:
def sumListRecur(L):
total = 0
for e in L:
if type(e) == type([]):
total += sumListRecur(e)
else:
total += e
return total
Honestly, except for the issue of depth, there doesn’t seem to be that much of a difference. In both cases, total scoops up all the values we need and returns the sum. And in the simplest case, where L is a flat list, there’s almost no difference at all - in both versions we use the else clause to add integers to total until we get the sum we’re after. But in the iterative version, there is only one total. Recall that when we are dealing with recursion, what we are really interested in is what happens within the frames, and that means that each frame has its own total!
As we’ve established, every time we recursively invoke sumListRecur(e) we create a new frame, to which we pass e as the argument. What does the state of function sumListRecur() in that frame look like? Exactly like the original sumListRecur(), with the difference that e is the parameter and not L. What this also means, however, is that total is set to 0 - after all, that’s what we asked the code to do. So how does this help our computation?
Think back on the discussion of how each frame in pal() held a different value of s. If I asked you, What is the value of s, you could only ask me to clarify, For which frame? Upon creation, each frame of pal() gets seeded with a different s. In the same way, the new frame of sumListRecur() gets seeded with e, but also total == 0. So if total is always 0, how can we add up anything?
This is where the base case comes in. Let’s say that L == [1, [2, 3]]. Since we’re running the function for the first time, this is the state of frame 1. The first run through the for e in L loop doesn’t have a recursive call, so at this point total == 1. The next run through the loop triggers the recursive call, sending e == [2, 3] to frame 2. In frame 2, we skip the if clause and iterate over the list, adding each item of e to total. Now frame 1 has total == 5. Finally, we get to return total, returning 5 to frame 1.
Where does that 5 wind up? In frame 1, in place of sumListRecur(e). It’s added to the current value of total, which is 1, yielding a sum of 6. Thanks to the final return total statement in frame 1, this is what is finally returned to the global frame.
Let’s add our usual print-tracing statements and see what this looks like for a larger L:
depth = 0
def sumListRecur(L):
total = 0
global depth
depth += 1
print('\ndepth =', depth)
print('total =', total)
for e in L:
print(' at top of for loop, next e =', e)
if type(e) == type([]):
print(' e =', e, 'is a list so recurse...')
r = sumListRecur(e)
total += r
print(' total is now =', total)
else:
total += e
print(' e =', e, 'is int so total =', total)
depth -= 1
print(' returning total =', total, 'to depth =', depth)
print('\ndepth =', depth)
return total
L = [1, [2, 3], [4, 5], 6]
print('depth =', depth, '\nL =', L)
print(sumListRecur(L))
>>> depth = 0 #global frame
>>> L = [1, [2, 3], [4, 5], 6]
>>> depth = 1 #frame 1
>>> total = 0
>>> at top of for loop, next e = 1
>>> e = 1 is int so total = 1 #total = 1
>>> at top of for loop, next e = [2, 3]
>>> e = [2, 3] is list so recurse...
>>> depth = 2 #frame 2
>>> total = 0
>>> at top of for loop, next e = 2
>>> e = 2 is int so total = 2
>>> at top of for loop, next e = 3
>>> e = 3 is int so total = 5
>>> returning total = 5 to depth = 1 #total = 5
>>> depth = 1 #frame 1
>>> at top of for loop, next e = [4, 5]
>>> e = [4, 5] is list so recurse...
>>> depth = 2 #frame 3
>>> total = 0
>>> at top of for loop, next e = 4
>>> e = 4 is int so total = 4
>>> at top of for loop, next e = 5
>>> e = 5 is int so total = 9
>>> returning total = 9 to depth = 1 #total = 9
>>> depth = 1 #frame 1
>>> at top of for loop, next e = 6
>>> e = 6 is int so total = 21
>>> returning total = 21 to depth = 0 #total = 21
>>> depth = 0 #global frame
>>> 21
In order to appreciate the importance of defining total as a variable that has local scope only, consider if we removed it from the function definition and just put it in the global frame, where it will be accessible from anywhere:
def sumListRecur(L, total):
for e in L:
if type(e) == type([]):
total += sumListRecur(e, total)
else:
total += e
return total
total = 0
L = [1, [2, 3], [4, 5]]
print(sumListRecur(L, total))
>>> 29
Another important trait of this code concerns frame creation. So far our examples have been rigorously predictable: the entire function’s work is inseparable from recursion. However, sumListRecur() only uses recursion when needed, and in some cases not at all. This implies that keeping track of frames is intrinsically different as well. We don’t have a monolithic structure for the function’s overall execution, but rather the type of each item in L tells us what to do.
You may have noticed in the above print-tracing code I didn’t explicitly track frames, preferring instead ‘depth’, or how many recursive calls were needed for each item in L. The fact is that depth and frame should really be tracked separately, since depth can be revisited, but frames are unique. For example, if L = [1, [2, 3], [4, 5], 6], for each item e in L we get:
e depth frame
1 1 1
[2, 3] 2 2
[4, 5] 2 3
6 1 1
We don’t close frame 1 until we have finished unpacking all sublists (ie, the end of the program). While [2, 3] and [4, 5] both have an additional level of depth, each frame is unique. We don’t ‘go back’ to frame 2 when we recurse ‘[4, 5]’ but create a new, third frame. This is important because I don’t want you to think that frame 2 still retains a value for total when in fact it’s been closed.
This may seem to be a trivial distinction, but we’ll see that it plays an important role when we encounter functions with multiple recursive calls, and also when we use depth (or ‘order’) to determine drawing the size of the next shape in a fractal, so just keep it in mind for the future.
Where’s the base case?¶
A final observation on this code: what happened to our base case? Going back to our basic template the base case is clear:
def foo(n):
if base case is True:
return base case
else:
return foo(#modified n)
You could just as easily point out pal()’s base case:
def foo(n):
if base case:
return True
else:
if #some condition:
return foo(#modified n)
else:
return False
But where is it in sumListRecur()?
def sumListRecur(L):
total = 0
for e in L:
if type(e) == type([]):
total += sumListRecur(e)
else:
total += e
return total
Quite simply, the base case is reached when the function executes all of its statements without triggering a recursive call. This is an interesting counterpoint to the other examples, where the base case is in the if portion of the if/else block. So one way to think about sumListRecur() and similar functions is its base case is when there is nothing left to execute but the last return statement. If this doesn’t seem intuitive at first, it’s OK - we’ll see this come up frequently in more advanced recursive algorithms.
To help you get more comfortable, here is a variation of sumListRecur(), where we aren’t summing a list of lists, but simply flattening L into a list without sublists:
def flatten(L):
newlist = []
for e in L:
if type(e) == type([]):
newlist.extend(flatten(e))
else:
newlist.append(e)
return newlist
print(flatten([2,9,[2,1,13,2],8,[2,6]]))
>>> [2,9,2,1,13,2,8,2,6]
Here, instead of total, we declare an empty list newList, but with exactly the same local scope and functionality. Another neat trick is that the result of the recursive call is the parameter used for the extend() list method.
Question: To better understand this code, ask yourself why we chose append() for one case, and extend() for the other?
Using recursion for directory listing¶
Recursing through lists has a very practical application as well. Consider being given the task of deriving a directory’s structure. You have access to the entire directory, but you have no idea how many folders are in it, nor how many subfolders may exist within any given folder. How do you print out the complete directory? This example may be a bit advanced compared to the code presented so far, but it’s worth the effrot.
Here is some code that leverages Python’s os module that prints out the directory listing for the Python folder in my local MacOS drive:
import os # can also be 'import os.path'
def get_dirlist(path):
"""
Return a sorted list of all entries in path.
This returns just names, not the full path to the names.
"""
dirlist = os.listdir(path)
dirlist.sort()
return dirlist
def print_files(path, prefix = ""):
""" Print recursive listing of contents of path """
if prefix == "": # Detect outermost call, print a heading
print("Folder listing for", path)
prefix = "| "
dirlist = get_dirlist(path)
for f in dirlist:
print(prefix + f) # Print the line
fullname = os.path.join(path, f) # Turn name into
full pathname
if os.path.isdir(fullname): # If a directory,
recurse.
print_files(fullname, prefix + "| ")
print(print_files('/Users/polis/py/3.6'))
This follows the template for flatten.py, where recursion is triggered when fullname is found to be a directory and not a file. I won’t be exhaustive about it, but let’s break this code down a bit further:
We use a number of methods that we import from the os module. When we call print_files() with a legal pathname, we first generate a header with no pipe. Since pipes are used for all subsequent prints, we immediately set prefix = '|'.
Calling dir_list() with path as its argument creates a new list dirlist from the os.listdir() module method, sorts it and returns it:
>>> Folder listing for /Users/polis/py/3.6/euler
>>> ['14_collatz', '.DS_Store', '12_triangle', '13_largesum', 'euler_diary_2019.txt'] #unsorted
>>> ['.DS_Store', '12_triangle', '13_largesum', '14_collatz', 'euler_diary_2019.txt'] #sorted
Note that os.listdir() returns a flat, unsorted list. Some of these may be files, others may be directories. If we want to see the directory structure in alphabetical order and not the way it is stored in memory then we have to return the sorted list:
>>> | 12_triangle
>>> ['triangle3.py', 'triangle2.py', 'triangle1.py'] #unsorted
>>> ['triangle1.py', 'triangle2.py', 'triangle3.py'] #sorted
>>> | | triangle1.py
>>> | | triangle2.py
>>> | | triangle3.py
>>> | | triangle4.py
Now we want to print out the items returned from get_dirlist(), which have been assigned to dirlist in print_files(). But if we just print them out as strings we have no way of knowing what is a file and what is a directory.
To do this, fullname = os.path.join(path, f) uses the join() method to concatenate the item f in dirlist with its pathname.
For example, if…
f == collatz6.py
…then fullname = os.path.join(path, f) returns:
/Users/polis/py/3.6/euler/14_collatz/collatz6.py
But we aren’t printing the entire pathname, so why would we do this? Because f may be either a file or a directory. Hence the recursive call:
fullname = os.path.join(path, f)
if os.path.isdir(fullname):
print_files(fullname, prefix + "| ")
This guarantees that we will print out the entire directory structure, and with each additional pipe showing the correct ‘depth’ of the directory structure.
Heuristics and Exercises¶
From this section, we can derive a number of helpful heuristics:
♦ Recursion doesn’t have to be the exclusive driver of the algorithm - it can be called on only when needed. But once it’s invoked, the recursive process must complete before the next computation can occur.
♦ A recursive call can happen anywhere within a function, and not just at the return statement. Binding the returned value of a recursive call to a variable allows us to capture the value and use it for further computation.
♦ The base case may not be an explicit value (eg, 1, or True), but simply the fact that the recursive case is no longer being called. As long as the program reaches a return statement without hitting a recursive call, the value being returned will reverse the recursive process.
Exercise: Given a list of lists that contains only numbers, write a recursive function find_min() that returns the smallest integer.
A good way to approach this problem is to first solve a smaller problem: How would you find - without using the min() method - the smallest value in a flat list? Once you’ve done that, consider how total functioned in sumListRecur(), and how you could integrate it with your approach to finding the minimum value into a recursive context.
Credit: Much of this material adapted from Chapter 18.2-3 of the fantastic resource, Think Like A Computer Scientist